package org.example.likou150.tree;

import java.util.HashMap;
import java.util.Map;

//先序遍历顺序：[根节点][左子树节点...][右子树节点...]
//
//中序遍历顺序：[左子树节点...][根节点][右子树节点...]
// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-interview-150
public class BuildTree {
    public static void main(String[] args) {
        // 前序
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
//        int[] preorder = new int[]{-1};
//        int[] inorder = new int[]{-1};
        BuildTree buildTree = new BuildTree();
        TreeNode treeNode = buildTree.buildTree(preorder, inorder);
        System.out.println(treeNode);
    }

//    int[] preorder = new int[]{3,9,20,15,7};
//    int[] inorder = new int[]{9,3,15,20,7};
    Map<Integer, Integer> inorderIndexMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构建值到索引的映射，加快查找
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        return build(preorder, 0, 0, preorder.length-1);
    }

    public TreeNode build(int[] preorder, int preBegin, int inBegin, int inEnd){
        if(inBegin > inEnd){
            return null;
        }
        int val = preorder[preBegin];
        TreeNode currentNode = new TreeNode(val);
        Integer inIndex = inorderIndexMap.get(val);

        currentNode.left = build(preorder, preBegin+1, inBegin, inIndex-1);
        currentNode.right = build(preorder, preBegin+inIndex-inBegin+1, inIndex+1, inEnd);
        return currentNode;
    }






     private class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;

         TreeNode() {
         }

         TreeNode(int val) {
             this.val = val;
         }

         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }
}
